package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description 唯一路径个数，每次只能向下或者向右走一个格。leetcode 第62题
 * @date 2023/10/4 16:58
 */
public class UniquePaths {

    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        arr[0][0] = 1; //从最开始的一个格子是  1种方法
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j - 1 >= 0 && i - 1 >= 0) {
                    arr[j][i] = arr[j - 1][i] + arr[j][i - 1]; //如果左边和上面都不为空，加上这两个
                } else if (j - 1 >= 0) {
                    arr[j][i] = arr[j - 1][i]; //上面不为空，等于上面的
                } else if (i - 1 >= 0) {
                    arr[j][i] = arr[j][i - 1]; //左面不为空，等于左面的
                }
            }
        }

        return arr[m - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(new UniquePaths().uniquePaths(3, 2));
        System.out.println(new UniquePaths().uniquePaths(3, 7));
    }
}
